/**
 * @Author: code.rookie
 * @ClassName: ConvertBSTToGreaterTree
 * @Date: 2021/11/1 11:06 上午
 * @PACKAGE_NAME: PACKAGE_NAME
 * @Version: 1
 * @Description 538. 把二叉搜索树转换为累加树
 */
public class ConvertBSTToGreaterTree {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            System.out.println("current root.val=" + root.val);
            convertBST(root.right);
            int cache = sum;
            sum += root.val;
            root.val = sum;
            System.out.println("sum=sum + root.val=" + cache + " + " + sum + ", root.val=sum=" + sum);
            convertBST(root.left);
        }
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
